package 分类.滑动窗口;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;

public class 找到字符串中所有字母异位词 {
    public List<Integer> findAnagrams(String s, String t) {
        HashMap<Character, Integer> need=new HashMap<>();
        HashMap<Character, Integer> window=new HashMap<>();
        int left=0,right=0;
        for (char c:t.toCharArray()){
            int num=need.getOrDefault(c,0);
            need.put(c,++num);
        }
        int vaild=0;
        List<Integer> res=new LinkedList<>();
        while (right<s.length()){
            char c=s.charAt(right);
            //右移窗口
            right++;
            if(need.containsKey(c)){
                int num=window.getOrDefault(c,0);
                window.put(c,++num);
                if(window.get(c)==need.get(c)){
                    vaild++;
                }
            }


            //判断是否要收缩
            while (right-left>t.length()){
                if(vaild==need.size()){
                   res.add(left);
                }
                char a=s.charAt(left);
                left++;
                if(need.containsKey(a)){
                    //先减少合法数量
                    if(window.get(a)==need.get(a)){
                        vaild--;
                    }
                    int num=window.getOrDefault(a,0);
                    window.put(a,--num);
                }
            }
        }
        return res;
    }
}
